package leetcode;

/**
 * 1292. 元素和小于等于阈值的正方形的最大边长     https://leetcode.cn/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold
 */
public class LeetCode1292 {

    public int maxSideLength(int[][] mat, int threshold) {
        int n = mat.length;
        int m = mat[0].length;
        // 前缀数组
        int[][] s = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] + mat[i - 1][j - 1] - s[i - 1][j - 1];
            }
        }
        // 累加
        for (int i = Math.min(n, m); i >= 1; i--) {
            for (int j = i; j <= n; j++) {
                for (int k = i; k <= m; k++) {
                    if (s[j][k] - s[j - i][k] - s[j][k - i] + s[j - i][k - i] <= threshold) {
                        return i;
                    }
                }
            }
        }
        return 0;
    }
}
